A production system, sometimes also called a “production rule system”, is a computing system which operates by checking trigger conditions defined in productions (also called “rules”) and then taking corresponding actions when the trigger conditions are met. Production rule systems are used, for example, in expert systems, business process management, automated planning, and other fields. Productions typically consist of two parts: a trigger condition (sometimes called the “IF portion” or “IF statement”) and a corresponding group of one more actions (also called the “THEN portion”). The trigger conditions typically involve a set of variables, sometimes called “working memory”, which contain data (sometimes called “facts” or “data tuples”) representing the states of pertinent real-world items. A rule engine (sometimes called a “rule interpreter”) compares the variables in working memory to the trigger conditions, fires rules whose trigger conditions are met, and takes the corresponding actions. It is not unusual for a taken action to modify the state of working memory, which may lead in turn to other rules being triggered, or to the same rule being triggered again with different facts.
One naive implementation of a rule interpreter would check a rule against known facts in the working memory database, fire the rule if the trigger condition is met, and then move on to the next rule, looping back to the first rule after all rules have been checked once in this iteration of the loop. In practice, this naive approach is not very efficient because part of a condition may be evaluated more often than necessary. An algorithm for comparing working memory to trigger conditions, known as the Rete algorithm, provides a more efficient approach. A rule engine using the Rete algorithm builds a network of nodes in which each node except the root corresponds to a pattern (also referred to here as a “partial condition”) in the IF portion of a rule. The path from the root node to a leaf node defines a complete rule trigger in terms of its component partial conditions. Each node has a memory of facts that satisfy the pattern, which tends to reduce the amount of evaluation performed to determine current fact values. A production's actions are still performed for each complete set of facts that match the production's conditions. Implementation of the Rete algorithm provides computing functionality that efficiently matches facts against productions in a pattern-matching production system rule engine. The Rete algorithm is widely used to implement pattern-matching functionality within computing system rule engines that use a match-resolve-act cycle to support forward chaining and inferencing.